/**
 *  Quick Sort
 *
 *  Time complexity:
 *  Space complexity
 */

import java.util.Arrays;
import java.util.Random;

class QuickSort2<E extends Comparable<E>> {

    public void sort(E[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int p = partition(a, lo, hi);

        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }

    private int partition(E[] a, int lo, int hi) {
        // Randomly pick a number
        int index = randomInt(lo, hi);
        E v = a[index];

        // Put it to the rear
        swap(a, index, hi);

        int left = lo;
        int right = hi;

        while (left < right) {
            if (a[left].compareTo(v) > 0) {
                swap(a, left, --right);
            } else {
                left++;
            }
        }

        // Put v back to a[left]
        swap(a, left, hi);

        return left;
    }

    private void swap(E[] a, int i, int j) {
        E tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private int randomInt(int lo, int hi) {
        Random rand = new Random();
        return rand.nextInt(hi - lo) + lo;
    }

}
